package leetcode.slidingwindow;

import java.util.Arrays;

//567. 字符串的排列
public class CheckInclusion {

    public static void main(String[] args) {
        String s1 = "ky", s2 = "ainwkckifykxlribaypk";
        System.out.println(checkInclusion2(s1, s2));
    }

    //滑动窗口
    public static boolean checkInclusion(String s1, String s2) {
        int[] need = new int[128];
        for (int i = 0; i < s1.length(); i++) {

            need[s1.charAt(i)]++;

        }
        int left = 0, right = 0, count = s1.length(), size = Integer.MAX_VALUE, start = 0;
        while (right < s2.length()) {
            char ch = s2.charAt(right);
            if (need[ch] > 0) {
                count--;
            }
            //如果不是要找的字符，将会被减成负数
            need[ch]--;
            if (count == 0) {

                while (need[s2.charAt(left)] < 0 && left < right) {
                    need[s2.charAt(left)]++;
                    left++;
                }
                if (right - left + 1 < size) {
                    size = right - left + 1;
                    start = left;
                }
                //扩大
                need[s2.charAt(left)]++;
                count++;
                left++;
            }
            right++;
        }
        return s1.length() == size;
    }

    //官方通用版本
    public static boolean checkInclusion2(String s1, String s2) {

        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        for (int i = 0; i < n; ++i) {
            cnt1[s1.charAt(i) - 'a']++;
            cnt2[s2.charAt(i) - 'a']++;
        }
        //判断s1和s2是不是相同的字符串
        if (Arrays.equals(cnt1, cnt2)) {
            return true;
        }
        for (int i = n; i < m; ++i) {
            //窗口向右移动，多统计一次进入窗口的字符
            cnt2[s2.charAt(i) - 'a']++;
            //窗口向右移动，少统计一次离开窗口的字符
            cnt2[s2.charAt(i - n) - 'a']--;
            if (Arrays.equals(cnt1, cnt2)) {
                return true;
            }
        }
        return false;
    }


}
